package com.yiwenup.leetcode.offer;

import com.yiwenup.leetcode.Node;

/**
 * https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/
 */
public class No036 {

    /**
     * 头节点
     */
    private Node head;

    /**
     * 记录前驱节点
     */
    private Node pre;

    /**
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：37.9 MB, 在所有 Java 提交中击败了26.75%的用户
     */
    public Node treeToDoublyList(Node root) {
        if (root == null) return null;

        inOrder(root);
        head.left = pre;
        pre.right = head;

        return head;
    }

    /**
     * 中序遍历实现
     */
    public void inOrder(Node node) {
        if (node == null) return;

        // 递归左子树
        inOrder(node.left);

        // 处理当前节点
        if (pre == null) {
            // 最左边叶子节点
            head = node;
        } else {
            pre.right = node;
        }
        node.left = pre;
        pre = node;

        // 递归右子树
        inOrder(node.right);
    }
}
